#include <cstdio>

using namespace std;

typedef long long ll;
const int maxn=1000000, mods=998244353;

ll qpow(ll a, int n) {
    ll s=1;
    for (; n; n/=2) {
        if (n&1) s=s*a%mods;
        a=a*a%mods;
    }
    return s;
}

ll fact[maxn+1], invf[maxn+1];

void initFact(int n) {
    fact[0] = 1;
    for (int i=1; i<=n; i++) fact[i] = fact[i-1]*i%mods;
    invf[n] = qpow(fact[n], mods-2);
    for (int i=n; i; i--) invf[i-1] = invf[i]*i%mods;
}

ll c(int n, int m) {
    return n<m ? 0 : fact[n]*invf[m]%mods*invf[n-m]%mods;
}

ll inv(int n) {return invf[n]*fact[n-1]%mods;}

int phi[maxn+1];
void initPhi(int n) {
    static bool book[maxn+1];
    static int pri[maxn+1];
    pri[0] = 0;
    book[1] = true;
    phi[1] = 1;
    for (int i=2; i<=n; i++) {
        if (!book[i]) {
            pri[++pri[0]] = i;
            phi[i] = i-1;
        }
        for (int j=1; j<=pri[0] && i*pri[j]<=n; j++) {
            book[i*pri[j]] = true;
            if (i%pri[j]==0) {
                phi[i*pri[j]] = phi[i]*pri[j];
                break;
            } else phi[i*pri[j]] = phi[i]*phi[pri[j]];
        }
    }
}

ll count(int n, int m, int k) {
    ll ans=0, flag=mods-1;
    for (int i=0; i<=n-m && i*(k+1)<=m; i++) {
        flag = mods-flag;
        ans = (ans+flag*c(n-m, i)%mods*c(n-i*(k+1)-1, m-i*(k+1))%mods)%mods;
    }
    return ans*n%mods*inv(n-m)%mods;
}

ll calc(int n, int m, int k) {
    ll ans=0;
    for (int i=1; i<=n; i++) {
        if (n%i==0 && m%i==0) {
            ans = (ans+count(n/i, m/i, k)*phi[i]%mods)%mods;
        }
    }
    return ans*inv(n)%mods;
}

int main() {
    freopen("gift.in", "r", stdin);
    freopen("gift.out", "w", stdout);

    initFact(maxn);
    initPhi(maxn);
    int t;
    scanf("%d", &t);

    for (int ti=1; ti<=t; ti++) {
        int n, m, k;
        scanf("%d %d %d", &n, &m, &k);
        printf("%lld\n", calc(n, m, k));
    }

    fclose(stdin);
    fclose(stdout);
    return 0;
}
